package com.wfm.niuke.duistackqueue;

import java.util.Arrays;
import java.util.Random;

public class BM47数组中的第K大的数字O076 {
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums,0,nums.length-1,nums.length-k);
    }
    public int quickSelect(int[] a, int l, int r, int index) {
        int q = randomPartition(a, l, r);
        if (q == index) {
            return a[q];
        } else {
            return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
        }
    }
    public int randomPartition(int[] a, int l, int r) {
        int i = random.nextInt(r - l + 1) + l;
        swap(a, i, r);
        return partition3(a, l, r);
    }
//    public int partition(int[] a, int l, int r) {
//        int x = a[r], i = l - 1;
//        for (int j = l; j < r; ++j) {
//            if (a[j] <= x) {
//                swap(a, ++i, j);
//            }
//        }
//        swap(a, i + 1, r);
//        return i + 1;
//    }
    // begin end 属于左闭右开区间[)
    int partition2(int[] arr, int begin, int end)
    {
        int pivot = arr[begin];
        while(begin < end)
        {
            while(begin < end && arr[--end] >= pivot);
            arr[begin] = arr[end];
            while(begin < end && arr[++begin] <= pivot);
            arr[end] = arr[begin];
        }
        arr[begin] = pivot;
        return begin;
    }

    // begin end 属于闭区间[]
    int partition3(int[] arr, int begin, int end)
    {
        int pivot = arr[begin];
        while(begin < end)
        {
            while(begin < end && arr[end] >= pivot) end--;
            arr[begin] = arr[end];
            while(begin < end && arr[begin] <= pivot) begin++;
            arr[end] = arr[begin];
        }
        arr[begin] = pivot;
        return begin;
    }
    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

//    public int findKthLargest(int[] nums, int k) {
//        int heapSize = nums.length;
//        buildMaxHeap(nums, heapSize);
//        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
//            swap(nums, 0, i);
//            --heapSize;
//            maxHeapify(nums, 0, heapSize);
//        }
//        return nums[0];
//    }
//
//    public void buildMaxHeap(int[] a, int heapSize) {
//        for (int i = heapSize / 2; i >= 0; --i) {
//            maxHeapify(a, i, heapSize);
//        }
//    }
//
//    public void maxHeapify(int[] a, int i, int heapSize) {
//        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
//        if (l < heapSize && a[l] > a[largest]) {
//            largest = l;
//        }
//        if (r < heapSize && a[r] > a[largest]) {
//            largest = r;
//        }
//        if (largest != i) {
//            swap(a, i, largest);
//            maxHeapify(a, largest, heapSize);
//        }
//    }
//
//    public void swap(int[] a, int i, int j) {
//        int temp = a[i];
//        a[i] = a[j];
//        a[j] = temp;
//    }

}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[] a = new int[]{4,5,3,6,2};
        Solution solution = new BM47数组中的第K大的数字O076().new Solution();
        int partition = solution.partition2(a, 0, a.length);
        System.out.println(Arrays.toString(a));
//        System.out.println(partition);
    }
}